package 算法.LeetCode91.每日打卡题目;

import java.util.*;

/**
 * @author: 谢君臣
 * @create: 2021-03-02 12:40
 * @founction: XXXX
 */
public class day28 {
    public static void main(String[] args) {
        maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
    }

    public int[] MaxSlidingWidow(int[]nums,int k){
        // 维护单调递减队列
        int n = nums.length;
        int[] ans = new int[n-k+1];
        Deque<Integer> decreQueue = new ArrayDeque<>();
        // 窗口左边界，包含
        int l = 1-k;
        // 窗口右边界，包含
        int r = 0;
        while (r < n){
            // 去除队列内无效的值，l是最低有效位，如果l比队列头部的坐标大，说明这个坐标已经过期
            if (!decreQueue.isEmpty() && l > decreQueue.peekFirst()){
                decreQueue.pollFirst();
            }
            // 维护单调递减队列
            while (!decreQueue.isEmpty() && nums[r] >= nums[decreQueue.peekLast()]){
                decreQueue.pollLast();
            }
            decreQueue.offerLast(r);
            // 在l>= 0的时候，窗口有效，开始填答案
            if (l >= 0){
                ans[l] = nums[decreQueue.peekFirst()];
            }
            l++;
            r++;
        }
        return ans;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] re = new int[nums.length-k+1];
        Deque<Integer> queue = new LinkedList();
        for (int i = 0; i < k; i++) {
            queue = DDqeue(queue,nums[i]);
        }
        re[0] = queue.peekFirst();
        queue = DDqeueremove(queue,nums[0]);
        for (int i = 0; i < nums.length-k; i++) {
            queue =DDqeue(queue,nums[i+k]);
            re[i+1] = queue.peekFirst();
            queue = DDqeueremove(queue,nums[i+1]);
        }
        return re;
    }
    public static Deque DDqeue(Deque<Integer> deque, int num){
        if (deque.isEmpty()||deque.peekLast()>= num)
            deque.add(num);
        else {
            Stack<Integer> stack = new Stack();
            while (!deque.isEmpty()&&deque.peekLast()<num){
                stack.push(deque.removeLast());
            }
            deque.add(num);
            while (!stack.isEmpty())
                deque.add(stack.pop());
        }
        return deque;
    }
    public static Deque DDqeueremove(Deque<Integer> deque, int num){
        if (deque.isEmpty())
            return deque;
        else {
            Stack<Integer> stack = new Stack();
            while (!deque.isEmpty()&&deque.peekLast()!=num){
                stack.push(deque.removeLast());
            }
            if (!deque.isEmpty())
                deque.removeLast();
            while (!stack.isEmpty())
                deque.add(stack.pop());
        }
        return deque;
    }
}
